package com.dkd.day20250614;

public class SolutionMerge {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead1 ListNode类
     * @param pHead2 ListNode类
     * @return ListNode类
     */
    public static ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // write code here

        //非空判断
        if (pHead1 == null) {
            return pHead2;
        }
        if (pHead2 == null) {
            return pHead1;
        }
        //前节点，记录最近的有序链表，假设cur为有序节点，next为比较节点
        ListNode start = pHead1;
        ListNode cur = null;
        ListNode next = null;
        ListNode pre = null;
        ListNode temp = null;
        //判断节点从谁开始
        if (pHead1.val <= pHead2.val) {
            pre = pHead1;
            start = pHead1;
            next = pHead1.next;
            pHead1.next = pHead2;
            cur = pHead2;

        }else{
            pre = pHead2;
            start = pHead2;
            next = pHead2.next;
            pHead2.next = pHead1;
            cur = pHead1;
        }
        int i =0;
        while (next != null) {
            if (cur.val < next.val) {
                //当前节点小于next节点，将cur节点的下一节点变为next，原next节点连载cur并变成cur
                temp = cur.next;
                pre = cur;
                cur.next = next;
                cur = cur.next;
                next = temp;
            }else{
                //当前节点大于next节点，将next节点插入cur与pre节点，next节点下移
                temp = next.next;
                pre.next = next;
                next.next=cur;
                pre = pre.next;
                next=temp;
            }
        }
        return start;
    }




    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(3);
        head1.next.next = new ListNode(5);
  //      head1.next.next.next = new ListNode(5);



        ListNode head2 = new ListNode(2);
        head2.next = new ListNode(4);
        head2.next.next = new ListNode(6);



        ListNode head = Merge(head1, head2);
        System.out.println(head.val);

        System.out.println("-------");
        while(head != null){
            System.out.println(head.val);
            head = head.next;
        }
    }
}
